1. Field
The present disclosure relates to computer systems and methods in which data resources are shared among data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the disclosure concerns a mutual exclusion mechanism known as “read-copy update.”
2. Description of the Prior Art
By way of background, read-copy update (also known as “RCU”) is a mutual exclusion technique that permits shared data to be accessed for reading without the use of locks, writes to shared memory, memory barriers, atomic instructions, or other computationally expensive synchronization mechanisms, while still permitting the data to be updated (modify, delete, insert, etc.) concurrently. The technique is well suited to both uniprocessor and multiprocessor computing environments wherein the number of read operations (readers) accessing a shared data set is large in comparison to the number of update operations (updaters), and wherein the overhead cost of employing other mutual exclusion techniques (such as locks) for each read operation would be high. By way of example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where read-side lock acquisition would be quite burdensome.
The read-copy update technique implements data updates in two phases. In the first (initial update) phase, the actual data update is carried out in a manner that temporarily preserves two views of the data being updated. One view is the old (pre-update) data state that is maintained for the benefit of read operations that may have been referencing the data concurrently with the update. The other view is the new (post-update) data state that is seen by operations that access the data following the update. In the second (deferred update) phase, the old data state is removed following a “grace period” that is long enough to ensure that the first group of read operations will no longer maintain references to the pre-update data. The second-phase update operation typically comprises freeing a stale data element to reclaim its memory. In certain RCU implementations, the second-phase update operation may comprise something else, such as changing an operational state according to the first-phase update.
FIGS. 1A-1D illustrate the use of read-copy update to modify a data element B in a group of data elements A, B and C. The data elements A, B, and C are arranged in a singly-linked list that is traversed in acyclic fashion, with each element containing a pointer to a next element in the list (or a NULL pointer for the last element) in addition to storing some item of data. A global pointer (not shown) is assumed to point to data element A, the first member of the list. Persons skilled in the art will appreciate that the data elements A, B and C can be implemented using any of a variety of conventional programming constructs, including but not limited to, data structures defined by C-language “struct” variables. Moreover, the list itself is a type of data structure.
It is assumed that the data element list of FIGS. 1A-1D is traversed (without locking) by multiple readers and occasionally updated by updaters that delete, insert or modify data elements in the list. In FIG. 1A, the data element B is being referenced by a reader r1, as shown by the vertical arrow below the data element. In FIG. 1B, an updater u1 wishes to update the linked list by modifying data element B. Instead of simply updating this data element without regard to the fact that r1 is referencing it (which might crash r1), u1 preserves B while generating an updated version thereof (shown in FIG. 1C as data element B′) and inserting it into the linked list. This is done by u1 acquiring an appropriate lock (to exclude other updaters), allocating new memory for B′, copying the contents of B to B′, modifying B′ as needed, updating the pointer from A to B so that it points to B′, and releasing the lock. In current versions of the Linux® kernel, pointer updates performed by updaters can be implemented using the rcu_assign_pointer( ) primitive. As an alternative to locking during the update operation, other techniques such as non-blocking synchronization or a designated update thread could be used to serialize data updates. All subsequent (post update) readers that traverse the linked list, such as the reader r2, will see the effect of the update operation by encountering B′ as they dereference B's pointer. On the other hand, the old reader r1 will be unaffected because the original version of B and its pointer to C are retained. Although r1 will now be reading stale data, there are many cases where this can be tolerated, such as when data elements track the state of components external to the computer system (e.g., network connectivity) and must tolerate old data because of communication delays. In current versions of the Linux® kernel, pointer dereferences performed by readers can be implemented using the rcu_dereference( ) primitive.
At some subsequent time following the update, r1 will have continued its traversal of the linked list and moved its reference off of B. In addition, there will be a time at which no other reader task is entitled to access B. It is at this point, representing an expiration of the grace period referred to above, that u1 can free B, as shown in FIG. 1D.
FIGS. 2A-2C illustrate the use of read-copy update to delete a data element B in a singly-linked list of data elements A, B and C. As shown in FIG. 2A, a reader r1 is assumed be currently referencing B and an updater u1 wishes to delete B. As shown in FIG. 2B, the updater u1 updates the pointer from A to B so that A now points to C. In this way, r1 is not disturbed but a subsequent reader r2 sees the effect of the deletion. As shown in FIG. 2C, r1 will subsequently move its reference off of B, allowing B to be freed following the expiration of a grace period.
In the context of the read-copy update mechanism, a grace period represents the point at which all running tasks (e.g., processes, threads or other work) having access to a data element guarded by read-copy update have passed through a “quiescent state” in which they can no longer maintain references to the data element, assert locks thereon, or make any assumptions about data element state. By convention, for operating system kernel code paths, a context switch, an idle loop, and user mode execution all represent quiescent states for any given CPU running non-preemptible code (as can other operations that will not be listed here). The reason for this is that a non-preemptible kernel will always complete a particular operation (e.g., servicing a system call while running in process context) prior to a context switch.
In FIG. 3, four tasks 0, 1, 2, and 3 running on four separate CPUs are shown to pass periodically through quiescent states (represented by the vertical bars). The grace period (shown by the dotted vertical lines) encompasses the time frame in which all four tasks that began before the start of the grace period have passed through one quiescent state. If the four tasks 0, 1, 2, and 3 were reader tasks traversing the linked lists of FIGS. 1A-1D or FIGS. 2A-2C, none of these tasks having reference to the old data element B prior to the grace period could maintain a reference thereto following the grace period. All post grace period searches conducted by these tasks would bypass B by following the updated pointers created by the updater.
RCU implementations may use a combining tree to track quiescent states, with bitmasks at each level of the tree indicating which CPU's quiescent states are required in order to end a grace period. This is known as hierarchical RCU. In hierarchical RCU implementations that support CPU hotplugging, additional bitmasks are provided at each level to indicate which CPU's are offline, and whose quiescent states are therefore not required to end a grace period. In current versions of the Linux® kernel, the RCU combining tree used for quiescent state tracking is implemented using an rcu_state structure that contains a tree of rcu_node structures embedded as a linear array. FIG. 4 illustrates an example two-level tree hierarchy that includes three bottom-level leaf rcu_node structures and a single top level root rcu_node structure. In a larger system with many CPUs, the combining tree could be expanded to include one or more additional levels of rcu_node structures.
The root rcu_node structure in FIG. 4 is reported to by the leaf rcu_node structures. Each leaf rcu_node structure is in turn reported to by a set of CPUs that periodically access their assigned leaf rcu_node structure to record RCU quiescent states. In FIG. 4, there are six CPUs represented by per-CPU rcu_data structures, with two CPUs being assigned to each leaf rcu_node structure. The rcu_data structures are used to maintain certain per-CPU RCU data, such as lists of RCU callbacks.
Although not shown, each of the four rcu_node structures in FIG. 4 has its own lock field, called ->lock. Each also includes the two bitmasks referred to above, respectively called ->qsmask and ->qsmaskinit. The ->qsmask bitmask tracks which CPUs (for leaf rcu_node structures) or groups of CPUs (for non-leaf rcu_node structures) still need to pass through a quiescent state in order for the current grace period to end. The ->qsmaskinit bitmask tracks which CPUs or groups of CPUs still need to pass through a quiescent state for subsequent grace periods to end. RCU's online/offline code manipulates the ->qsmaskinit bitmask, such that this bitmask tracks which CPUs or groups of CPUs are offline. At the beginning of each grace period, the ->qsmaskinit fields are copied to the corresponding ->qsmask fields. Offline CPUs are thereby accounted for in the detection of current grace periods, and will be ignored so as not stall such grace periods (by waiting indefinitely for quiescent states from the offline CPUs).
Modern RCU implementations feature update primitives such as synchronize_rcu( ) to wait for a grace period to elapse in which all pre-existing readers have completed their critical sections. In the older “classic” RCU implementation in the Linux® kernel, RCU read-side critical sections cannot block or be preempted, so all the reader tasks that synchronize_rcu( ) must wait on are running on one of the CPUs. However, in the more recent real-time preemptible implementation of RCU, RCU read-side critical sections may be preempted, which means that synchronize_rcu( ) may also need to wait on tasks that are currently not running.
To track preempted tasks, each leaf rcu_node structure in the preemptible RCU implementation is provided with a ->blkd_tasks list, which is a linked list of tasks that were preempted within an RCU read-side critical section while running on one of the CPUs corresponding to that rcu_node structure. A given task is added to the list when it is preempted, and it removes itself from the list once it exits from its outermost RCU read-side critical section. If a given RCU grace period extends for too long, then in kernels built with RCU priority boosting, those tasks on the ->blkd_tasks list that are blocking the current grace period will be subjected to RCU priority boosting.
The ->lock field in each rcu_node structure is used to protect operations involving tasks on that rcu_node structure's ->blkd_tasks list. Such operations include (1) inserting a task onto the ->blkd_tasks list when the task is preempted while within an RCU read-side critical section, (2) updating the task state to record RCU priority boosting, and (3) removing the task from the ->blkd_tasks list when the task exits its outermost RCU read-side critical section. Note that tasks on the ->blkd_tasks list that entered their RCU read-side critical sections before the start of the current RCU grace period must prevent that grace period from completing. Tasks on the ->blkd_tasks list that entered their RCU read-side critical sections after the start of the current RCU grace period must prevent a subsequent grace period from completing.
Once all of the CPUs corresponding to a given rcu_node structure have gone offline, it is desirable to ignore that rcu_node structure for grace period detection purposes. However, there is no guarantee that an rcu_node structure's ->blkd_tasks list will be empty because the corresponding tasks might still be preempted, or might even be continuing to execute within their RCU read-side critical sections on some other CPU(s). There must therefore be some mechanism to ensure that these tasks continue to block the current or subsequent RCU grace period (as the case may be) despite the corresponding rcu_node structure being ignored during grace period detection.
In older versions of the Linux® kernel, this mechanism involved offlining the last CPU corresponding to a given leaf rcu_node structure, and migrating the tasks in the leaf rcu_node structure's ->blkd_tasks list to a ->blkd_tasks list of the root rcu_node structure. The tasks can only be migrated one at a time because each task's locking domain must be switched from the leaf rcu_node structure to root rcu_node structure. Otherwise, unsynchronized access could corrupt the root rcu_node structure's ->blkd_tasks list.
Unfortunately, the above-described list migration must be carried out with interrupts disabled, which can affect real time performance. Moreover, each ->blkd_tasks list can be quite long, so that migrating them can result in arbitrary degradation of real-time latencies. This was not considered a problem when the above-described task-migration mechanism was designed. At that time, it was expected that real-time systems would avoid offlining CPUs while a real-time application was running. However, recent real-time best practices include offlining a given CPU and then bringing it back online in order to remove extraneous processing from that CPU, thereby providing better real-time response to applications running on the CPU. Furthermore, today's multi-core systems motivate the running of multiple real-time applications on a single system, which means that one CPU might be being offlined and then onlined while a real-time application is running on another CPU.
The inventor named herein has observed a need for a hierarchical RCU grace period detection mechanism that correctly handles CPU hotplugging while avoiding excessive degradation of real-time latency. What is required in particular is a hierarchical RCU grace period detection technique that avoids the delays associated with the above-described task-migration mechanism.